Search Results

Documents authored by Kolman, Petr

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.41
How to Cut a Ball Without Separating: Improved Approximations for Length Bounded Cut

Authors: Eden Chlamtáč and Petr Kolman

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
The Minimum Length Bounded Cut problem is a natural variant of Minimum Cut: given a graph, terminal nodes s,t and a parameter L, find a minimum cardinality set of nodes (other than s,t) whose removal ensures that the distance from s to t is greater than L. We focus on the approximability of the problem for bounded values of the parameter L. The problem is solvable in polynomial time for L ≤ 4 and NP-hard for L ≥ 5. The best known algorithms have approximation factor ⌈ (L-1)/2⌉. It is NP-hard to approximate the problem within a factor of 1.17175 and Unique Games hard to approximate it within Ω(L), for any L ≥ 5. Moreover, for L = 5 the problem is 4/3-ε Unique Games hard for any ε > 0. Our first result matches the hardness for L = 5 with a 4/3-approximation algorithm for this case, improving over the previous 2-approximation. For 6-bounded cuts we give a 7/4-approximation, improving over the previous best 3-approximation. More generally, we achieve approximation ratios that always outperform the previous ⌈ (L-1)/2⌉ guarantee for any (fixed) value of L, while for large values of L, we achieve a significantly better ((11/25)L+O(1))-approximation. All our algorithms apply in the weighted setting, in both directed and undirected graphs, as well as for edge-cuts, which easily reduce to the node-cut variant. Moreover, by rounding the natural linear programming relaxation, our algorithms also bound the corresponding bounded-length flow-cut gaps.
Cite as

Eden Chlamtáč and Petr Kolman. How to Cut a Ball Without Separating: Improved Approximations for Length Bounded Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chlamtac_et_al:LIPIcs.APPROX/RANDOM.2020.41,
  author =	{Chlamt\'{a}\v{c}, Eden and Kolman, Petr},
  title =	{{How to Cut a Ball Without Separating: Improved Approximations for Length Bounded Cut}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.41},
  URN =		{urn:nbn:de:0030-drops-126446},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.41},
  annote =	{Keywords: Approximation Algorithms, Length Bounded Cuts, Cut-Flow Duality, Rounding of Linear Programms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.18
Extension Complexity, MSO Logic, and Treewidth

Authors: Petr Kolman, Martin Koutecký, and Hans Raj Tiwary

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We consider the convex hull P_phi(G) of all satisfying assignments of a given MSO_2 formula phi on a given graph G. We show that there exists an extended formulation of the polytope P_phi(G) that can be described by f(|phi|,tau)*n inequalities, where n is the number of vertices in G, tau is the treewidth of G and f is a computable function depending only on phi and tau. In other words, we prove that the extension complexity of P_phi(G) is linear in the size of the graph G, with a constant depending on the treewidth of G and the formula phi. This provides a very general yet very simple meta-theorem about the extension complexity of polytopes related to a wide class of problems and graphs.
Cite as

Petr Kolman, Martin Koutecký, and Hans Raj Tiwary. Extension Complexity, MSO Logic, and Treewidth. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kolman_et_al:LIPIcs.SWAT.2016.18,
  author =	{Kolman, Petr and Kouteck\'{y}, Martin and Tiwary, Hans Raj},
  title =	{{Extension Complexity, MSO Logic, and Treewidth}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.18},
  URN =		{urn:nbn:de:0030-drops-60405},
  doi =		{10.4230/LIPIcs.SWAT.2016.18},
  annote =	{Keywords: Extension Complexity, FPT, Courcelle's Theorem, MSO Logic}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.129
Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing

Authors: Petr Kolman and Christian Scheideler

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
An elementary h-route flow, for an integer h >= 1, is a set of h edge-disjoint paths between a source and a sink, each path carrying a unit of flow, and an h-route flow is a non-negative linear combination of elementary h-route flows. An h-route cut is a set of edges whose removal decreases the maximum h-route flow between a given source-sink pair (or between every source-sink pair in the multicommodity setting) to zero. The main result of this paper is an approximate duality theorem for multicommodity $h$-route cuts and flows, for h <= 3: The size of a minimum h-route cut is at least f/h and at most O(log^3(k)f) where f is the size of the maximum h-route flow and k is the number of commodities. The main step towards the proof of this duality is the design and analysis of a polynomial-time approximation algorithm for the minimum h-route cut problem for h=3 that has an approximation ratio of O(log^3 k). Previously, polylogarithmic approximation was known only for $h$-route cuts for h <= 2. A key ingredient of our algorithm is a novel rounding technique that we call multilevel ball-growing. Though the proof of the duality relies on this algorithm, it is not a straightforward corollary of it as in the case of classical multicommodity flows and cuts. Similar results are shown also for the sparsest multiroute cut problem.
Cite as

Petr Kolman and Christian Scheideler. Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 129-140, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kolman_et_al:LIPIcs.STACS.2011.129,
  author =	{Kolman, Petr and Scheideler, Christian},
  title =	{{Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{129--140},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.129},
  URN =		{urn:nbn:de:0030-drops-30051},
  doi =		{10.4230/LIPIcs.STACS.2011.129},
  annote =	{Keywords: Multicommodity flow, Multiroute flow, Cuts, Duality}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact